package basic.study.wantOffer.chapter3;

import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @ClassName Problem32
 * @Description 从上往下打印二叉树
 * @Company inspur
 * @Author Kevin
 * @Date 2020/5/19 16:45
 * @Version 1.0
 */
public class Problem32 {
    /**
     * 不分行从上往下打印二叉树
     */
    public void printTree1(BinaryTreeNode root) {
        if (root == null) return;

        Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
        queue.offer(root);
        BinaryTreeNode node;
        while (!queue.isEmpty()) {
            node = queue.poll();
            System.out.println(node.value + " ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    /**
     * 分行打印从上往下打印二叉树
     */
    public void pringTree2(BinaryTreeNode root) {
        if (root == null) return;

        Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
        queue.offer(root);
        BinaryTreeNode node;

        while (!queue.isEmpty()) {
            //分层
            int size = queue.size();
            //对每一层
            while (size >0) {
                node = queue.poll();
                System.out.println(node.value + " ");
                size--;

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }
    /**
     * 借助霜栈法，之字形打印二叉树
     */
    public void printTree3(BinaryTreeNode root) {
        if (root == null) return;

        Stack<BinaryTreeNode> stack1 = new Stack<BinaryTreeNode>();
        Stack<BinaryTreeNode> stack2 = new Stack<BinaryTreeNode>();

        stack1.push(root);
        BinaryTreeNode node;

        while (!stack1.empty() || !stack2.empty()) {
            while (!stack1.empty()) {
                node = stack1.pop();
                System.out.println(node.value + " ");
                if (node.left != null) stack2.push(node.left);
                if (node.right != null) stack2.push(node.right);
            }
            System.out.println();
            while(!stack2.empty()) {
                node = stack2.pop();
                System.out.println(node.value + " ");
                if (node.right != null) stack1.push(node.right);
                if (node.left != null) stack2.push(node.left);
            }
            System.out.println();
        }
    }
}
